πŸ‘©β€πŸ’» 42862. 체윑볡

@Seongukbaek Posted April 20, 2022 Β· Updated April 20, 2022 Β· 5 min read

문제

μ μ‹¬μ‹œκ°„μ— 도둑이 λ“€μ–΄, 일뢀 학생이 μ²΄μœ‘λ³΅μ„ λ„λ‚œλ‹Ήν–ˆμŠ΅λ‹ˆλ‹€. λ‹€ν–‰νžˆ μ—¬λ²Œ 체윑볡이 μžˆλŠ” 학생이 μ΄λ“€μ—κ²Œ μ²΄μœ‘λ³΅μ„ 빌렀주렀 ν•©λ‹ˆλ‹€. ν•™μƒλ“€μ˜ λ²ˆν˜ΈλŠ” 체격 순으둜 맀겨져 μžˆμ–΄, λ°”λ‘œ μ•žλ²ˆν˜Έμ˜ ν•™μƒμ΄λ‚˜ λ°”λ‘œ λ’·λ²ˆν˜Έμ˜ ν•™μƒμ—κ²Œλ§Œ μ²΄μœ‘λ³΅μ„ λΉŒλ €μ€„ 수 μžˆμŠ΅λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄, 4번 학생은 3번 ν•™μƒμ΄λ‚˜ 5번 ν•™μƒμ—κ²Œλ§Œ μ²΄μœ‘λ³΅μ„ λΉŒλ €μ€„ 수 μžˆμŠ΅λ‹ˆλ‹€. 체윑볡이 μ—†μœΌλ©΄ μˆ˜μ—…μ„ 듀을 수 μ—†κΈ° λ•Œλ¬Έμ— μ²΄μœ‘λ³΅μ„ 적절히 빌렀 μ΅œλŒ€ν•œ λ§Žμ€ 학생이 μ²΄μœ‘μˆ˜μ—…μ„ λ“€μ–΄μ•Ό ν•©λ‹ˆλ‹€.

전체 ν•™μƒμ˜ 수 n, μ²΄μœ‘λ³΅μ„ λ„λ‚œλ‹Ήν•œ ν•™μƒλ“€μ˜ λ²ˆν˜Έκ°€ λ‹΄κΈ΄ λ°°μ—΄ lost, μ—¬λ²Œμ˜ μ²΄μœ‘λ³΅μ„ κ°€μ Έμ˜¨ ν•™μƒλ“€μ˜ λ²ˆν˜Έκ°€ λ‹΄κΈ΄ λ°°μ—΄ reserveκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, μ²΄μœ‘μˆ˜μ—…μ„ 듀을 수 μžˆλŠ” ν•™μƒμ˜ μ΅œλŒ“κ°’μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μž‘μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • 전체 ν•™μƒμ˜ μˆ˜λŠ” 2λͺ… 이상 30λͺ… μ΄ν•˜μž…λ‹ˆλ‹€.
  • μ²΄μœ‘λ³΅μ„ λ„λ‚œλ‹Ήν•œ ν•™μƒμ˜ μˆ˜λŠ” 1λͺ… 이상 nλͺ… μ΄ν•˜μ΄κ³  μ€‘λ³΅λ˜λŠ” λ²ˆν˜ΈλŠ” μ—†μŠ΅λ‹ˆλ‹€.
  • μ—¬λ²Œμ˜ μ²΄μœ‘λ³΅μ„ κ°€μ Έμ˜¨ ν•™μƒμ˜ μˆ˜λŠ” 1λͺ… 이상 nλͺ… μ΄ν•˜μ΄κ³  μ€‘λ³΅λ˜λŠ” λ²ˆν˜ΈλŠ” μ—†μŠ΅λ‹ˆλ‹€.
  • μ—¬λ²Œ 체윑볡이 μžˆλŠ” ν•™μƒλ§Œ λ‹€λ₯Έ ν•™μƒμ—κ²Œ μ²΄μœ‘λ³΅μ„ λΉŒλ €μ€„ 수 μžˆμŠ΅λ‹ˆλ‹€.
  • μ—¬λ²Œ μ²΄μœ‘λ³΅μ„ κ°€μ Έμ˜¨ 학생이 μ²΄μœ‘λ³΅μ„ λ„λ‚œλ‹Ήν–ˆμ„ 수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λ•Œ 이 학생은 μ²΄μœ‘λ³΅μ„ ν•˜λ‚˜λ§Œ λ„λ‚œλ‹Ήν–ˆλ‹€κ³  κ°€μ •ν•˜λ©°, 남은 체윑볡이 ν•˜λ‚˜μ΄κΈ°μ— λ‹€λ₯Έ ν•™μƒμ—κ²ŒλŠ” μ²΄μœ‘λ³΅μ„ λΉŒλ €μ€„ 수 μ—†μŠ΅λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

n lost reserve return
5 [2, 4] [1, 3, 5] 5
5 [2, 4] [3] 4
3 [3] [1] 2

πŸ“ Logic

for (int l : lost) { if (map.containsKey(l)) map.computeIfPresent(l, (k, v) -> v - 1); else lostMap.put(l, 0); } for (int l : lostMap.keySet()) { if (map.containsKey(l - 1) && map.get(l - 1) > 0) { map.computeIfPresent(l - 1, (k, v) -> v - 1); map.put(l, 0); } else if (map.containsKey(l + 1) && map.get(l + 1) > 0) { map.computeIfPresent(l + 1, (k, v) -> v - 1); map.put(l, 0); } else map.put(l, -1); }
  • 학생과 체윑볡 개수 정보λ₯Ό Map 으둜 μ €μž₯ν•œλ‹€.

    • reserve 에 μžˆλŠ” 학생듀은 λͺ¨λ‘ 체윑볡 수λ₯Ό 1개둜 μ§€μ •ν•œλ‹€.
  • λ¨Όμ € lost 와 reserve λ‘˜ 닀에 μžˆλŠ” ν•™μƒμ˜ κ²½μš°λŠ” 자기 μ²΄μœ‘λ³΅μ„ μžκΈ°κ°€ 써야 ν•˜λ―€λ‘œ, μ²΄μœ‘λ³΅μ„ λ„λ‚œλ‹Ήν•œ 학생 λͺ©λ‘μΈ lostMap 에 λ„£μ§€ μ•Šκ³ , ν•΄λ‹Ή ν•™μƒμ˜ 체윑볡 μˆ˜λŠ” 0으둜 updateν•œλ‹€.
  • lostMap μ—λŠ” 이제 μ²΄μœ‘λ³΅μ„ λΉŒλ €μ•Ό ν•˜λŠ” ν•™μƒλ“€λ§Œ μ‘΄μž¬ν•œλ‹€.

    • μ•ž 번호의 ν•™μƒλ“€μ—κ²Œ 빌릴 수 μžˆλŠ”μ§€ ν™•μΈν•˜κ³ , 체윑볡 개수 정보λ₯Ό μˆ˜μ •ν•œλ‹€.
  • μ΅œμ’…μ μœΌλ‘œ 체윑볡 κ°œμˆ˜κ°€ 0 이상인 ν•™μƒλ“€μ˜ 수λ₯Ό μ„Όλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { int[] possible; public int solution(int n, int[] lost, int[] reserve) { Arrays.sort(lost); Arrays.sort(reserve); Map<Integer, Integer> map = new HashMap<>(); Map<Integer, Integer> lostMap = new HashMap<>(); for (int r : reserve) map.put(r, 1); for (int l : lost) { if (map.containsKey(l)) map.computeIfPresent(l, (k, v) -> v - 1); else lostMap.put(l, 0); } for (int l : lostMap.keySet()) { if (map.containsKey(l - 1) && map.get(l - 1) > 0) { map.computeIfPresent(l - 1, (k, v) -> v - 1); map.put(l, 0); } else if (map.containsKey(l + 1) && map.get(l + 1) > 0) { map.computeIfPresent(l + 1, (k, v) -> v - 1); map.put(l, 0); } else map.put(l, -1); } int answer = 0; for (int i = 1; i <= n; i++) { if (map.containsKey(i) && map.get(i) < 0) continue; answer++; } return answer; } }

✏️ Review

  • κ·Έλ¦¬λ””λŠ” 이해도 μ•ˆλ˜κ³ , μ½”λ“œλ„ μ•ˆ 이쁜 것 κ°™λ‹€.
  • 쑴재 μ—¬λΆ€λ₯Ό ν™•μΈν•˜κΈ° μœ„ν•œ Map 은 μœ μš©ν•œ 것 κ°™λ‹€.

πŸ“• 좜처

Programmers : https://programmers.co.kr/learn/courses/30/lessons/42862

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€